package leetcodes;

import com.sun.org.apache.xalan.internal.xsltc.dom.AdaptiveResultTreeImpl;
import node.ListNode;
import sun.plugin2.message.GetAppletMessage;

import java.util.*;

public class Main1 {

    public static void main(String[] args) {
        String str1 = "abcedf";
        String str2 = "cedf";
    }

    //求两个字符串最长公共子串的长度
    public static int getLongestSubString(String str1,String str2){
        //暴力求解
        if (str1==null || str2==null){
            return 0;
        }
        int res = 0;
        int len1= str1.length();
        int len2 = str2.length();
        for (int a=0;a<len1;a++){
            for (int b=0;b<len2;b++){
                int x=a,y=b;
                int tempMax = 0;
                while (x<len1 &&y<len2){
                    if (str1.charAt(x) == str2.charAt(y)){
                        tempMax++;
                        x++;
                        y++;
                    }else{
                        res = Math.max(res,tempMax);
                    }
                    break;
                }

            }
        }
        return res;
    }



    /*
    * 给定一个数组，数组中任意两个不同的数字，以及这两个数字下标差，三条边构成一个桶，求最大容量桶
    * */
    public static int maxArea(int[] height) {
        //双指针法
        int begin = 0;
        int end= height.length-1;
        int res = -1;
        while (begin<end){
            int min = Math.min(height[begin],height[end]);
            int tempA = (end - begin) *min;
            res = Math.max(res,tempA);
            if (min == height[begin]){
                begin++;
            }else {
                end--;
            }
        }
        return res;

        /*
        暴力循环法
        int max = -1;
        for (int a=0;a<height.length-1;a++){
            for (int b=a+1;b<height.length;b++){
                int res = (b-a)*Math.min(height[a],height[b]);
                System.out.println(res);
                max = Math.max(max,res);
            }
        }
        return max;*/
    }


    //反转整数
    public static int reverse(int x) {
        int f = 0;
        if (x ==0){
            return 0;
        }
        if (x<0){
            f=1;
            x = x*-1;
        }

        ArrayList<Integer> arr= new ArrayList<>();
        while (x>0){
            arr.add(x%10);
            x = x/10;
        }
        int res = 0;
        for (int a=0;a<arr.size();a++){
            res = (res*10) + arr.get(a);
        }
        if (res > (int)Math.pow(2,29)-1){
            return 0;
        }
        return f==1?(res*-1):res;
    }

    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int a=0;a<array.length;a++){
            int val = 1;
            if (map.containsKey(array[a])){
                val++;
            }
            map.put(array[a],val);
        }
        Iterator<Integer> it = map.keySet().iterator();
        ArrayList<Integer> arr = new ArrayList<>();
        while (it.hasNext()){
            int key =it.next();
            if (map.get(key) ==1){
                arr.add(key);
            }
        }
        num1[0] = arr.get(0);
        num2[0] = arr.get(1);
    }

    public static ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        TreeMap<Integer,ArrayList<Integer>>  map = new TreeMap<>();
        ArrayList<Integer> arr = new ArrayList<>();
        for (int a= 0;a<array.length-1;a++){
            for (int b=a+1;b<array.length;b++){
                if (array[a] + array[b] ==sum){
                    System.out.println(array[a] + "  "+array[b]);
                    arr = new ArrayList<>();
                    arr.add(array[a]);
                    arr.add(array[b]);
                    map.put(array[a] * array[b],arr);
                }
            }
        }
        return map.size()==0?arr:map.get(map.keySet().iterator().next());
    }

    public static double Power(double base, int exponent) {
        double a = 1d;
        int exp = 0;
        if (exponent < 0){
            exponent = exponent *-1;
            exp = 1;
        }
        for (int x = 0; x < exponent; x++) {
            a = a * base;
        }

        return exp == 1 ? (1/a) : a;
    }


    /*
    * 一个升序数组，其中会出现重复的数字，请返回k的个数
    * */
    public static int GetNumberOfK(int [] array , int k) {
        int begin = 0;
        int end = array.length;
        int res = -1;
        while (begin<end){
            int mid = (begin+end)/2;
            if (k==array[mid]){
                res =mid;
            }
            if (k<array[mid]){
                end = mid -1;
            }
            if (k>array[mid]){
                begin = mid+1;
            }
        }
        int count = 1;
        if (res!=-1){
            int x = res;
            while (array[x]!=array[res]){
                x++;
                count++;
            }
            int y = res;
            while (array[y]!=array[res]){
                y++;
                count++;
            }

        }
        return count == 1? -1:count;
    }




    /*
    * 二维数组代表购买价格和使用价值
    * */
    public static int getMaxValue(int sum,int[][] arrs,int index){
        //空间不足了
        if (sum<=0){
            return 0;
        }
        //货物完了
        if (index == arrs.length){
            return 0;
        }
        int p1=getMaxValue(sum, arrs, index+1);
        int p2=Integer.MIN_VALUE;
        int p3=Integer.MIN_VALUE;
        if (sum>=arrs[index][0]){  //如果背包有足够空间
            //选取当前货物 后续获得的最高价值
            p2=arrs[index][1]+getMaxValue(sum-arrs[index][0], arrs,index+1 );
            p3=arrs[index][1]+getMaxValue(sum-arrs[index][0], arrs,index);
        }
        int max = 0;
        max = max<p1?p1:max;
        max = max<p2?p2:max;
        max = max<p3?p3:max;
        return max;
    }

    /**
     * 返回亲7数个数
     * @param digit int整型一维数组 组成亲7数的数字数组
     * @return int整型
     * 112
     */
   /* public static int reletive_7 (int[] digit) {
        // write code here
        StringBuilder stringBuilder = new StringBuilder();
        for (int a:digit){
            stringBuilder.append(a);
        }
        int res =0;
        for (String str:Permutation(stringBuilder.toString())){
            if (Integer.parseInt(str) % 7 ==0){
                res++;
            }
        }
        return res;
    }*/



    public static int StrToInt(String str) {
        char[] chars = str.toCharArray();
        boolean begin = false;
        int res = 0;
        for (int a= 0;a<chars.length;a++){
            char c = chars[a];
            if (!begin && c=='+' || c=='-' || c=='0'){
                continue;
            }
            if (begin ){
                if (c=='-'){
                    res = res*(-1);
                }
                return 0;
            }
            if (c=='1' || c=='2' ||c=='3' ||c=='4' ||c=='5' ||c=='6' ||c=='7' ||c=='8' ||c=='9' ||c=='0'){
                int x = (int)c-48;
                System.out.println("x:"+x);
                res=(res*10)+x;
                System.out.println("res:"+res);
                begin = true;
            }
        }
        return res;
    }



    /*
    * 使用递归 每次返回当前状态下可以到达的数
    * */
    public static int movingCount(int threshold, int rows, int cols)
    {
        boolean[] visited=new boolean[rows*cols];
        return movingCountCore(threshold, rows, cols, 0,0,visited);
    }
    private static int movingCountCore(int threshold, int rows, int cols,
                                int row,int col,boolean[] visited) {
        if(row<0||row>=rows||col<0||col>=cols) return 0;
        int i=row*cols+col;
        if(visited[i]||!getArrive(threshold,row,col)) return 0;
        visited[i]=true;
        return 1+movingCountCore(threshold, rows, cols,row,col+1,visited)
                +movingCountCore(threshold, rows, cols,row,col-1,visited)
                +movingCountCore(threshold, rows, cols,row+1,col,visited)
                +movingCountCore(threshold, rows, cols,row-1,col,visited);
    }

    public static boolean getArrive(int threshold, int rows, int cols){
        int num = 0;
        while (rows >9){
            num+=rows%10;
            rows = rows/10;
        }
        num+=rows;
        while (cols >9){
            num+=cols%10;
            cols = cols/10;
        }
        num+=cols;
        return num<=threshold? true:false;
        /*
        * int sum=0;
        while(row!=0){
            sum+=row%10;
            row=row/10;
        }
        while(col!=0){
            sum+=col%10;
            col=col/10;
        }
        if(sum>threshold) return false;
        return true;
        * */
    }



    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement) && map.get(complement) != i) {
                return new int[] { i, map.get(complement) };
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }





    public static void appendSonStr(String s,ArrayList<String> strings,int index){
        if (index >= s.length()){
            return;
        }
        appendSonStr(s,strings,index+1);
        String res = deleteByIndex(s,index);
        strings.add(res);
        appendSonStr(res,strings,index);
    }
    public static String deleteByIndex(String s,int index){
        StringBuilder stringBuilder = new StringBuilder();
        char[] chars = s.toCharArray();
        for (int a=0;a<chars.length;a++){
            if (a!=index){
                stringBuilder.append(chars[a]);
            }
        }
        return stringBuilder.toString();
    }
}
